package ds

// SmallHeap 小顶堆
type SmallHeap struct {
	Lists []*ListNode
}

func (h *SmallHeap) Init() {
	for i := len(h.Lists)/2 - 1; i >= 0; i-- {
		h.adjustHeap(i, len(h.Lists)-1)
	}
}

func (h *SmallHeap) PushHeap(node *ListNode) {
	h.Lists = append(h.Lists, node)
	insertIndex := len(h.Lists) - 1
	parentIndex := (insertIndex - 1) / 2
	for parentIndex >= 0 && h.Lists[parentIndex].Val > node.Val {
		h.Lists[insertIndex] = h.Lists[parentIndex]
		h.Lists[parentIndex] = node
		insertIndex = parentIndex
		parentIndex = (insertIndex - 1) / 2
	}
}

func (h *SmallHeap) PopHeap() *ListNode {
	res := h.Lists[0]
	h.Lists[0] = h.Lists[len(h.Lists)-1]
	h.Lists = h.Lists[:len(h.Lists)-1]
	h.adjustHeap(0, len(h.Lists)-1)
	return res
}

func (h *SmallHeap) adjustHeap(start int, end int) {
	if start >= end {
		return
	}

	index := start
	tempNode := h.Lists[start]
	for index*2+1 <= end {
		leftChild := index*2 + 1
		rigthChild := leftChild + 1
		if rigthChild <= end && h.Lists[rigthChild].Val < h.Lists[leftChild].Val {
			if tempNode.Val > h.Lists[rigthChild].Val {
				h.Lists[index] = h.Lists[rigthChild]
				index = rigthChild
			} else {
				break
			}
		} else {
			if tempNode.Val > h.Lists[leftChild].Val {
				h.Lists[index] = h.Lists[leftChild]
				index = leftChild
			} else {
				break
			}
		}
	}

	//最终插入的位置
	h.Lists[index] = tempNode
}

func (h *SmallHeap) IsEmpty() bool {
	return len(h.Lists) == 0
}
